\documentclass[a4paper,12pt]{article}

\usepackage[utf8x]{inputenc}
\usepackage[L7x]{fontenc}
\usepackage[lithuanian]{babel}
\usepackage[left=3cm,top=2cm,right=3cm,bottom=3cm,nohead,foot=1.5cm]{geometry}
\usepackage{graphicx}
\usepackage{setspace}

%\onehalfspacing

\title{Masugo --- maksimalių dažnų pografių paieškos įrankis}
\author{Kliment Olechnovič}
\date{2011}

\begin{document}

\maketitle

\tableofcontents
\newpage


\section{Įvadas}
Pristatau programinį įrankį, pavadintą {\em Masugo}, atliekantį maksimalių dažnų pomedžių ir pografių paiešką grafų aibėje.
Šiame dokumente trumpai apžvelgiami programoje įgyvendinti algoritmai, pateikiamos programos panaudojimo instrukcijos.
Taip pat pateikiami rezultatai eksperimentų, atliktų su cheminių junginių ir baltymų struktūrų grafų aibėmis.


\section{Pagrindinės sąvokos}

\subsection{Pažymėti grafai}
Masugo dirba su pažymėtais (angl. labelled) grafais. {\em Pažymėtas grafas} yra toks neorientuotas grafas,
kuriame kiekvienai viršūnei ir kiekvienai briaunai priskirta žymė, nebūtinai unikali.
Pažymėtas grafas gali būti apibrėžtas kaip
ketvertas $G=(V, E, L, \delta)$ kur:
\begin{itemize}
  \item $V$ yra viršūnių aibė
  \item $E \subseteq V \times V$ yra briaunų aibė
  \item $L$ yra žymių aibė
  \item $\delta : (V \cup E) \rightarrow L$ yra funkcija, kuri priskiria žymes viršūnėms ir briaunoms
\end{itemize}
Pažymėtų grafų pavyzdžiai pavaizduoti paveiksle \ref{fig:lgsi}.
Toliau tekste pažymėtus grafus kartais vadinsiu tiesiog grafais.

\subsection{Pažymėtų grafų izomorfizmas ir izomorfiniai pografiai}
Dviejų pažymėtų grafų $A$ ir $B$ {\em izomorfizmas} yra tokia bijekcija  $f : V_A \rightarrow V_B$, kad teisingi šie teiginiai:
\begin{itemize}
  \item $\forall v \in V_A$, $\delta_A(e)=\delta_B(f(v))$
  \item $\forall (v,u) \in E_A$, $(f(v),f(u)) \in E_B$ ir $\delta_A(v,u)=\delta_B(f(v),f(u))$
\end{itemize}
Pažymėtas grafas $A$ vadinamas pažymėto grafo $B$ {\em izomorfiniu pografiu}, jeigu egzistuoja izomorfizmas $f : V_A \rightarrow V_C$, kur $C$ yra pažymėto grafo $B$ pografis.
Tada sakoma, kad grafas $B$ {\em palaiko} grafą $A$.
Izomorfinių pografių pavyzdžiai pavaizduoti paveiksle \ref{fig:lgsi}.
Toliau tekste pažymėtų grafų izomorfinius pografius kartais vadinsiu tiesiog pografiais.

\begin{figure}
	\centering
	\includegraphics[scale=0.7]{img/labelled_graph_subgraph_isomorphism.png}
	\caption {P, Q ir S yra pažymėti grafai. Q ir S yra P izomorfiniai pografiai. Paveikslas paimtas iš \cite{Huan2004}.}
	\label{fig:lgsi}
\end{figure}

\subsection{Maksimalūs dažni pografiai}
Tarkime, duota grafų aibė $\Omega$ ir skaičius $0 < \sigma \leq 1$, vadinamas
{\em palaikymo slenksčiu}. Tada {\em dažnu pografiu} vadinamas bet koks grafas $A$, kurį palaiko ne mažiau $|\Omega|*\sigma$ grafų iš $\Omega$.
Pažymėkime grafų aibės $\Omega$ dažnų pografių aibę kaip $\Psi$.
Tada {\em maksimaliu dažnu pografiu} vadinamas bet koks grafas $A \in \Psi$, kurį palaiko tik vienas grafas iš $\Psi$ --- pats $A$.


\section{Maksimalių dažnų pografių paieška}

\subsection{Uždavinys}
Maksimalių dažnų pografių paieškos uždavinys --- duotai grafų aibei ir palaikymo slenksčiui surasti visus maksimalius dažnus pografius.

\subsection{Bendra schema}
Masugo įgyvendintas algoritmas atitinka SPIN metodo straipsnyje \cite{Huan2004} aprašytą bendrąją schemą,
pagal kurią grafų aibėje ieškoma dažnų pomedžių, o paskui kiekvienam dažnam pomedžiui ieškoma maksimalių dažnų pografių,
priklausančių to pomedžio ekvivalentiškumo klasei. SPIN straipsnyje \cite{Huan2004} pateikta schema įgyvendinta naudojantis
straipsniuose \cite{Chi2003, Chi2005, Yan2002, Zhao2008} pateiktais algoritmais ir idėjomis.

\subsection{Dažnų pomedžių paieška}

\subsubsection{Pažymėto medžio kanoninė forma}
Jungus beciklis grafas vadinamas {\em laisvu medžiu} (angl. free tree).
Jungus beciklis grafas, kurio viena viršūnė laikoma šaknimi, vadinamas {\em šaknuotu medžiu} (angl. rooted tree).
Šaknuotas medis, kuriam apibrėžta viršūnių apėjimo tvarka pradedant nuo šaknies,
vadinamas {\em sutvarkytu šaknuotu medžiu} (angl. ordered rooted tree) arba medžio {\em kanonine forma} (angl. canonical form).
Procedūra, kuri laisvą medį paverčia sutvarkytu šaknuotu medžiu, vadinama {\em medžio normalizavimu}.
Masugo įgyvendinta normalizavimo procedūra, aprašyta straipsniuose \cite{Chi2003, Chi2005}.
Ji susideda iš medžio šaknies išskirimo (pav. \ref{fig:rt}) ir medžio sutvarkymo (pav. \ref{fig:rto}).
Medžio sutvarkymo procedūroje briaunų žymės laikomos viršūnių žymių dalimis.
Pasirinktas kanoninės medžio formos konstravimo metodas leidžia paprastai išskaičiuoti
visus medžio automorfizmus (izomorfizmus į save), tai iliustruoja paveikslas \ref{fig:autom}.

\begin{figure}
	\centering
	\includegraphics[scale=0.9]{img/root_selection.png}
	\caption {Medžio šaknies išskirimas. Paveikslas paimtas iš \cite{Chi2005}.}
	\label{fig:rt}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[scale=0.9]{img/rooted_tree_ordering.png}
	\caption {Šaknuoto medžio sutvarkymas. Paveikslas paimtas iš \cite{Chi2005}.}
	\label{fig:rto}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[scale=0.9]{img/automorphisms.png}
	\caption {Medžio automorfizmų išskaičiavimas. Paveikslas paimtas iš \cite{Chi2005}.}
	\label{fig:autom}
\end{figure}

\subsubsection{Pažymėto medžio kanoninė eilutė}
Galima apeiti pažymėtą sutvarkytą šaknuotą medį į gylį (DFT - depth first traversal) arba į plotį (BFT - breadth first traversal)
ir užrašyti aptiktų viršūnių žymes į vieną eilutę specialiu formatu, kaip parodyta straipsniuose \cite{Chi2003, Chi2005, Huan2004}.
Gauta eilutė vadinama pažymėto medžio {\em kanonine eilute}.
Pavyzdžiui, apėjus paveiksle \ref{fig:rto} pavaizduotą pažymėtą sutvarkytą šaknuotą medį DFT būdu, gaunama eilutė ``ABCF\$ G\$\$ DE\$\$\$ BDE\$\$\$ B\#'',
o apėjus jį BFT būdu, gaunama eilutė ``A\$ B\$ B\$ B\$ CD\$ D\$ FG\$ E\$ E\#''.
Yra įrodyta, kad dviejų medžių $A$ ir $B$ kanoninės eilutės sutampa tada ir tik tada kai $A$ ir $B$ yra izomorfiški \cite{Chi2003, Chi2005}.

\subsubsection{Dažnų pomedžių išskaičiavimo algoritmas}
Masugo įgyvendintas dažnų pomedžių išskaičiavimo (angl. enumeration) algoritmas daugiausia paremtas
straipsnyje \cite{Zhao2008} pateiktu algoritmu. Paveiksle \ref{fig:et} pavaizduotas virtualus išskaičiavimo medis.
Jis pradedamas konstruoti nuo vienos viršūnės dydžio dažnų pomedžių. Išskaičiavimo medis auginamas ``depth-first''
principu, nauji lapai konstruojami pridedant prie jau rastų dažnų pomedžių po vieną viršūnę ir briauną --- tam atminyje laikinai saugomi pomedžių atvaizdai grafų aibėje (pav. \ref{fig:sc}).
Auginant dažnus pomedžius atsižvelgiama į jų automorfizmus (pav. \ref{fig:abp}).
Pomedžių pasikartojimai atpažįstami kanoninių eilučių pagalba --- kanoninės eilutės naudojamos kaip ``hash'' raktai.
Dažni pomedžiai pažymimi kaip maksimalūs jeigu iš jų negalima gauti kitų dažnų pomedžių.

\begin{figure}
	\centering
	\includegraphics[scale=0.9]{img/enumeration_tree.png}
	\caption {Dažnų pomedžių išskaičiavimo medis. Paveikslas paimtas iš \cite{Zhao2008}.}
	\label{fig:et}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[scale=0.9]{img/support_counting.png}
	\caption {Pomedžių atvaizdai grafų aibėje. Paveikslas paimtas iš \cite{Chi2005}.}
	\label{fig:sc}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[scale=0.9]{img/automorphism_pruning.png}
	\caption {Medžių automorfizmo problemos iliustracija --- pridedant lapus prie skirtingų viršūnių gaunami izomorfiški medžiai. Paveikslas paimtas iš \cite{Zhao2008}.}
	\label{fig:abp}
\end{figure}

\subsection{Maksimalių dažnų pografių konstravimas iš dažnų pomedžių}

\subsubsection{Aprėpiančiais medžiais paremtos grafų ekvivalentiškumo klasės}
Vietoje paveiksle \ref{fig:rt} iliustruojamo medžio šaknies išskirimo algoritmo galima naudoti kitą,
kuris šaknimi pavadina tokią viršūne, kad ją atitinkančio sutvarkyto šaknuoto medžio kanoninė eilutė būtų maksimali,
t.y. kad nebūtų galima gauti leksikografiškai didesnės kanoninės eilutės su bet kokia kita šaknimi.
Turint medžių aibę, galima iš jos pasirinkti tokį medį, kurio kanoninė eilutė leksikografiškai didžiausia.
Kiekvienas grafas turi vieną ar daugiau aprėpiančių medžių. Didžiausią iš jų kanoninių eilučių straipsnio \cite{Huan2004}
autoriai siūlo laikyti grafo ekvivalentiškumo klasės identifikatoriumi. Tokios eilutės suradimui taikomas godus algoritmas.
Sakoma, kad grafas $G$ priklauso medžio $M$ ekvivalentiškumo klasei, jei grafo $G$ didžiausia galima aprėpiančio medžio kanoninė eilutė
lygi medžio $M$ kanoninei eilutei. Paveiksle \ref{fig:eqcl} pavaizduoti keli ekvivalentiškumo klasių pavyzdžiai.

\subsubsection{Medžio ekvivalentiškumo klasei priklausančių maksimalių dažnų pografių išskaičiavimas}
Straipsnyje \cite{Huan2004} pateiktas medžio ekvivalentiškumo klasei priklausančių
maksimalių dažnų pografių išskaičiavimo algoritmas (pav. \ref{fig:eqce}) idėjiškai panašus į dažnų pomedžių išskaičiavimo algoritmą.
Pagrindinis skirtumas --- vietoje išorinių briaunų naudojamos vidinės briaunos, t.y. briaunos tarp nagrinėjamo medžio viršūnių.
Vietoje kanoninių eilučių naudojamos pridedamų vidinių briaunų aibes identifikuojančios eilutės.
Taip pat pritaikytos optimizacijos, susijusios su asociatyviomis išorinėmis ir vidinėmis briaunomis \cite{Huan2004}.


\begin{figure}
	\centering
	\includegraphics[scale=0.9]{img/equivalence_classes.png}
	\caption {Kelios aprėpiančiais medžiais paremtos grafų ekvivalentiškumo klasės. Paveikslas paimtas iš \cite{Huan2004}.}
	\label{fig:eqcl}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[scale=0.9]{img/equivalence_class_enumeration.png}
	\caption {Medžio ekvivalentiškumo klasei priklausančių grafų išskaičiavimo iliustracija. Paveikslas paimtas iš \cite{Huan2004}.}
	\label{fig:eqce}
\end{figure}


\section{Programos naudojimas}

\subsection{Kompiliavimas}
Masugo išeities kodą galima atsisiųsti iš Google Code SVN repozitorijaus:
\begin{verbatim}
svn checkout http://masugo.googlecode.com/svn/trunk/ masugo-read-only
\end{verbatim}
Programai sukompiliuoti reikalingas C++ kompiliatorius,
palaikantis C++ Technical Report 1 (TR1) standartinės bibliotekos plėtinį (būtinos tik klasės {\em unordered\_map} ir {\em unordered\_set}).
Pavyzdžiui, tinka g++ kompiliatorius 4.1 ar naujesnis.
Programa kompiliuojama viena eilute:
\begin{verbatim}
g++ -O3 src/main.cpp -o masugo
\end{verbatim}

\subsection{Paleidimas}
Masugo paleidimas be parametrų išveda trumpas paleidimo instrukcijas.
Normaliam Masugo paleidimui reikalingi du privalomi parametrai - failo su grafų aibe
vardas ir palaikymo (angl. support) slenksčio reikšmė, pavyzdžiui:
\begin{verbatim}
./masugo --file chemical --support 0.1
\end{verbatim}
Papildomai galima nurodyti, kad programa atliktų kelias paieškas,
kas žingsnį mažindama minimalaus palaikymo reikšmę:
\begin{verbatim}
./masugo --file chemical --support 0.3 --steps 10 --step-size 0.02
\end{verbatim}
Be to, galima nurodyti, kad programa ieškotų tik maksimalių dažnų pomedžių (tai
daroma greičiau):
\begin{verbatim}
./masugo --file chemical --support 0.1 --only-subtrees
\end{verbatim}
Masugo spausdina informacinius pranešimus į {\em stdout},
klaidų pranešimus į {\em stderr} ir užrašo visus rastus pomedžius ir pografius į failus.
Išvedimo failų vardai sudaromi prie įvedimo failo vardo pridedant galūnes.
Plačiau apie įvedimo ir išvedimo formatus galima sužinoti atsisiuntus pavyzdžius iš masugo.googlecode.com


\section{Eksperimentai}

\subsection{Motyvų paieška cheminiuose junginiuose}
Pritaikiau Masugo dviems cheminių junginių grafų aibėms, ,,compound'' ir ,,chemical''.
Šios aibės platinamos kartu su gSpan \cite{Yan2002} programa.
Pritaikymo rezultatai yra failuose compound.tar.gz bei chemical.tar.gz iš masugo.googlecode.com.
Paveikslai \ref{fig:cmpar} ir \ref{fig:char} iliustruoja kiekybinius ,,compound'' ir ,,chemical'' aibių analizės rezultatus.

\begin{figure}
	\centering
	\includegraphics[scale=0.4]{img/compound_log_plot_st_fst.png}
	\includegraphics[scale=0.4]{img/compound_log_plot_st_mfst.png}
	\includegraphics[scale=0.4]{img/compound_log_plot_st_mfsg.png}
	\includegraphics[scale=0.4]{img/compound_log_plot_st_t.png}
	\includegraphics[scale=0.4]{img/compound_log_plot_st_t-fst.png}
	\caption {Kiekybiniai ,,compound'' aibės analizės rezultatai.}
	\label{fig:cmpar}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[scale=0.4]{img/chemical_log_plot_st_fst.png}
	\includegraphics[scale=0.4]{img/chemical_log_plot_st_mfst.png}
	\includegraphics[scale=0.4]{img/chemical_log_plot_st_mfsg.png}
	\includegraphics[scale=0.4]{img/chemical_log_plot_st_t.png}
	\includegraphics[scale=0.4]{img/chemical_log_plot_st_t-fst.png}
	\caption {Kiekybiniai ,,chemical'' aibės analizės rezultatai.}
	\label{fig:cmpar}
\end{figure}

\subsection{Motyvų paieška baltymų struktūruose}
Kitos dvi grafų aibės, ,,pdexk'' ir ,,cullpdb\_pc20\_res18'', yra sugeneruotos su kita mano programa, Cocadus (dar nepublikuota),
skaičiuojančia tarpatominių kontaktų plotus baltymų struktūruose --- joje naudojamiems metodams pailiustruoti skirtas
vizualizacijos įrankis Voroprot \cite{Olechnovic2011}.

Trumpai apžvelgsiu pažymėto grafo konstravimą.
Duotai baltymo struktūrai tarpatominių kontaktų plotai skaičiuojami
iš visų baltymo struktūros atomų sferų Voronoi diagramos \cite{Olechnovic2011} (pav. \ref{fig:aav}).
Tolimesnei analizei paliekami tik kontaktai tarp šoninės grandinės atomų.
Paskui tarpatominiai kontaktai grupuojami pagal tai, kokioms aminorūgštims jie priklauso.
Galiausiai gaunamas pažymėtas grafas, kurio viršūnių žymės yra aminorūgščių vardai (ALA, VAL, PHE ir kiti --- iš viso 20),
o brianos gali turėti žymę 0 arba 1 --- 0 jei kontaktuojančios aminorūgštys sujungtos peptidiniu ryšiu, 1 kitais atvejais.

\begin{figure}
	\centering
	\includegraphics[scale=0.4]{img/amino_acids_voronoi.png}
	\caption {Baltymo struktūros Voronoi diagramos dalis. Skirtingomis spalvomis pažymėtos skirtingo aminorūgštys.}
	\label{fig:aav}
\end{figure}

Grafų aibė ,,pdexk'' yra nedidelė, sudaryta iš 34 vienos baltymų šeimos (PDEXK) atstovu.
Aibė ,,cullpdb\_pc20\_res18'' yra žymiai didesnė --- ji sudaryta iš 2428 aukštos kokybės baltymų struktūrų rinkinio,
kuris sudarytas Dunbrack laboratorijoje (http://dunbrack.fccc.edu/).
Maksimalus sekos panašumas tarp bet kokių dviejų baltymų šiame rinkinyje neviršija 20\%, todėl galima tikėtis,
kad jis neblogai atstovauja visų šiandien žinomų baltymų struktūrų aibę.

Pritaikymo rezultatai yra failuose pdexk.tar.gz bei cullpdb\_pc20\_res18.tar.gz iš masugo.googlecode.com.
Paveikslai \ref{fig:cpdbar} ir \ref{fig:pdexkar} iliustruoja kiekybinius ,,cullpdb\_pc20\_res18'' ir ,,pdexk'' aibių analizės rezultatus.
Paveiksluose \ref{fig:cpdbex} ir \ref{fig:pdexkex} pateikti rastų pografių pavyzdžiai:  du ,,cullpdb\_pc20\_res18'' aibėje dažni pografiai ir du ,,pdexk'' aibėje dažni pografiai.
Plačiau rezultaus tikiuosi aptarti per prezentaciją.

\begin{figure}
	\centering
	\includegraphics[scale=0.4]{img/cullpdb_pc20_res18_subgraph_1.png}
	\includegraphics[scale=0.4]{img/cullpdb_pc20_res18_subgraph_2.png}
	\caption {Du ,,cullpdb\_pc20\_res18'' aibėje dažni pografiai (palaikymo slenkstis lygus 0.5).}
	\label{fig:cpdbex}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[scale=0.4]{img/pdexk_subgraph_1.png}
	\includegraphics[scale=0.4]{img/pdexk_subgraph_2.png}
	\caption {Du ,,pdexk'' aibėje dažni pografiai (palaikymo slenkstis lygus 0.4).}
	\label{fig:pdexkex}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[scale=0.4]{img/cullpdb_pc20_res18_log_plot_st_fst.png}
	\includegraphics[scale=0.4]{img/cullpdb_pc20_res18_log_plot_st_mfst.png}
	\includegraphics[scale=0.4]{img/cullpdb_pc20_res18_log_plot_st_mfsg.png}
	\includegraphics[scale=0.4]{img/cullpdb_pc20_res18_log_plot_st_t.png}
	\includegraphics[scale=0.4]{img/cullpdb_pc20_res18_log_plot_st_t-fst.png}
	\caption {Kiekybiniai ,,cullpdb\_pc20\_res18'' aibės analizės rezultatai.}
	\label{fig:cpdbar}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[scale=0.4]{img/pdexk_log_plot_st_fst.png}
	\includegraphics[scale=0.4]{img/pdexk_log_plot_st_mfst.png}
	\includegraphics[scale=0.4]{img/pdexk_log_plot_st_mfsg.png}
	\includegraphics[scale=0.4]{img/pdexk_log_plot_st_t.png}
	\includegraphics[scale=0.4]{img/pdexk_log_plot_st_t-fst.png}
	\caption {Kiekybiniai ,,pdexk'' aibės analizės rezultatai.}
	\label{fig:pdexkar}
\end{figure}

\section{Įšvados}
Programa suskurta ir išbandyta.
Ji pasirodė pritaikoma svarbioje srityje --- baltymų struktūrų analizėje.

\newpage
\bibliographystyle{plain}
\addcontentsline{toc}{section}{Literatūra}
\bibliography{references}

\end{document}
